package com.dxb.test.sort;

/**
 * 快速排序
 * 基本思想：（分治）
 * 先从数列中取出一个数作为key值；
 * 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
 * 对左右两个小数列重复第二步，直至各区间只有1个数。
 * <p>
 * 辅助理解：挖坑填数
 * 初始时 i = 0; j = 9; key=72
 * 由于已经将a[0]中的数保存到key中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
 * 从j开始向前找一个比key小的数。当j=8，符合条件，a[0] = a[8] ; i++ ; 将a[8]挖出再填到上一个坑a[0]中。
 * 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。
 * 这次从i开始向后找一个大于key的数，当i=3，符合条件，a[8] = a[3] ; j-- ; 将a[3]挖出再填到上一个坑中。
 */
public class QuickSort extends BaseSort {
    public QuickSort(int[] array) {
        super(array);
    }

    @Override
    public void sort() {
        qsort(0, length - 1);
    }

    private void qsort(int low, int high) {
        if (low >= high) {
            return;
        }
        //将数组分为两部分
        int pivot = partition(low, high);
        //递归排序左子数组
        qsort(low, pivot - 1);
        //递归排序右子数组
        qsort(pivot + 1, high);
    }

    private int partition(int low, int high) {
        //基准
        int pivot = array[low];
        while (low < high) {
            // 从右向左找第一个小于x的数
            while (high > low && array[high] > pivot) {
                high--;
            }
            if (high > low) {
                array[low++] = array[high];
            }
            // 从左向右找第一个大于x的数
            while (high > low && array[low] < pivot) {
                low++;
            }
            if (high > low) {
                array[high--] = array[low];
            }
        }
        array[low] = pivot;
        return low;
    }

    public static void main(String args[]) {
        int[] array = {99, 78, 26, 17, 82, 36, 9, 81, 22, 100, 30, 20, 17, 85};
        QuickSort qs = new QuickSort(array);
        qs.run();
    }
}
